"""
    这是排序算法代码
"""

# 快速排序
def quick_sort(lst):
    n = len(lst)
    if n <= 1:
        return lst
    
    baseline = lst[0]  # 设置轴值
    # 移动轴值
    left = [lst[i] for i in range(1, len(lst)) if lst[i] < baseline]
    right = [lst[i] for i in range(1, len(lst)) if lst[i] >= baseline]

    return quick_sort(left) + [baseline] + quick_sort(right)  # 递归 调用


# 冒泡排序
def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(1, n - i):
            if lst[j - 1] > lst[j]:
                lst[j - 1], lst[j] = lst[j], lst[j - 1]  # 交换一下元素
    return lst


# 归并排序
def merge_sort(lst):
    #   两归并序列比较排序成一个有序序列
    def merge(left,right):
        i = 0
        j = 0   
        result = []    
        while i < len(left) and j < len(right):  
            if left[i] <= right[j]:    
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result = result + left[i:] + right[j:]  #    如果归并段还有剩余元素，加入到结果序列
        return result
    
    n = len(lst)
    if n <= 1:     
        return lst
    mid = n // 2  #   整数除法
    left = merge_sort(lst[:mid])  #   左序列继续归并
    right = merge_sort(lst[mid:])  #   右序列继续归并
    return merge(left,right)  #    分配结束后两两合并


# 堆排序
def heap_sort(lst):
    def adjust_heap(lst, i, size):
        left_index = 2 * i + 1
        right_index = 2 * i + 2
        largest_index = i 
        if left_index < size and lst[left_index] > lst[largest_index]: 
            largest_index = left_index 
        if right_index < size and lst[right_index] > lst[largest_index]: 
            largest_index = right_index 
        if largest_index != i: 
            lst[largest_index], lst[i] = lst[i], lst[largest_index] 
            adjust_heap(lst, largest_index, size)
 
    def built_heap(lst, size):
        for i in range(len(lst)//2)[::-1]: 
            adjust_heap(lst, i, size) 
 
    size = len(lst)
    built_heap(lst, size) 
    for i in range(len(lst))[::-1]:         
        lst[0], lst[i] = lst[i], lst[0]
        adjust_heap(lst, 0, i) 
    return lst



# 插入排序
def insertion_sort(lst):
    for i in range(len(lst) - 1):
        cur_num, pre_index = lst[i+1], i
        while pre_index >= 0 and cur_num < lst[pre_index]:
            lst[pre_index + 1] = lst[pre_index]
            pre_index -= 1
        lst[pre_index + 1] = cur_num 
    return lst


# 选择排序
def selection_sort(lst):
    for i in range(len(lst) - 1):  
        min_index = i  #   设置标志位
        for j in range(i + 1, len(lst)):
            if lst[j] < lst[min_index]:
                min_index = j  #   如果顺序不对记录下标志位
        lst[i], lst[min_index] = lst[min_index], lst[i]  #   交换元素位置
    return lst
